package leetcode;

import java.util.Random;

import list.LinkedListCreate;
import list.ListNode;

public class LinkedListRandomNode {

	public static void main(String[] args) {
		int[] array = {1, 2, 3, 4, 5};
		ListNode head = LinkedListCreate.createList(array);
		System.out.println(head.val);
		for(int i = 0; i < 20; i++){
			LinkedListRandomNode object = new LinkedListRandomNode(head);
			System.out.println(object.getRandom());
		}
	}
	
	//蓄水池算法
	//初始，只有一个数据的时候，返回该数据，有两个数据的时候，我们返回两个中的一个
	//生成一个0,1的随机数，然后决定1的时候替换数据
	//遇到第三个数据的时候，生成0, 1, 2的随机数，同样是2的话进行替换
	//那么此时返回1 ： 1 / 2 * 2 / 3 = 1 /3；
	//返回2： 1 / 2 * 2 / 3 = 1 /3；
	//返回3： 1 / 3
	
	private ListNode head;
	private Random random;
	public LinkedListRandomNode(ListNode head) {
		this.head = head;
		random = new Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
    	ListNode res = null;
    	int length = 1;
		ListNode temp = head;
        while(temp != null){
        	int i = random.nextInt(length);
        	//System.out.println("random: " + i);
        	if(i == length - 1){
        		res = temp;
        	}
        	temp = temp.next;
        	length++;
        }
        return res.val;
    }
}
